package william.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author ZhangShenao
 * @date 2024/1/15
 * @description <a href="https://leetcode.cn/problems/binary-tree-inorder-traversal/description/">...</a>
 */
public class Leetcode94_二叉树的中序遍历 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public List<Integer> inorderTraversal(TreeNode root) {
        //边界条件校验
        if (root == null) {
            return Collections.emptyList();
        }

        return inorderTraversalIteration(root);
    }

    /**
     * 递归实现
     * 首先对左子树进行中序遍历,然后访问根节点,最后对右子树进行中序遍历
     */
    private void inorderTraversalRecursive(TreeNode root, List<Integer> result) {
        //递归终止条件
        if (root == null) {
            return;
        }

        //首先对左子树进行中序遍历
        inorderTraversalRecursive(root.left, result);

        //然后访问根节点
        result.add(root.val);

        //最后对右子树进行中序遍历
        inorderTraversalRecursive(root.right, result);
    }

    /**
     * 迭代实现
     * 借助一个栈,一路寻找左子树,并将沿途的根节点保存到栈中
     */
    private List<Integer> inorderTraversalIteration(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();

        //从根节点开始迭代二叉树
        while (root != null || !stack.empty()) {
            //一路寻找左子树,并将沿途的根节点保存到栈中
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            //循环结束,将根节点弹栈
            root = stack.pop();

            //访问根节点
            result.add(root.val);

            //继续处理右子节点
            root = root.right;
        }

        //返回结果
        return result;
    }
}
